import java.util.Arrays;

/**
 * 归并排序。
 * @authur: 杨亚旭 891217573@qq.com
 * @date: 2019/3/18 18:41
 **/
public class MergeSort {

    public static void merge(int array[],int start,int mid,int end){
        int tmp[]=new int[end-start+1];
        int i =start;
        int j=mid+1;
        int k=0;

        while (i<=mid && j<=end){
            if(array[i]<= array[j]){
                tmp[k++] =array[i++];
            }else {
                tmp[k++] =array[j++];
            }
        }
        while (i<= mid){
            tmp[k++] =array[i++];
        }
        while (j<=end){
            tmp[k++] =array[j++];
        }

        for (i=0;i<k;i++){
            array[start+i]=tmp[i];
        }
        tmp=null;
    }

    public static void mergeSortUp2Down(int array[],int start,int end){
        if(array==null || start>=end){
            return;
        }
        //取中间值
        int mid=(end+start)>>>1;
        mergeSortUp2Down(array,start,mid);
        mergeSortUp2Down(array,mid+1,end);
        merge(array,start,mid,end);
    }

    public static void mergeGroups(int array[],int length,int gap){
        int i;
        int twolen = 2 * gap;
        for(i = 0; i+2*gap-1<length;i+=(2*gap))
            merge(array,i,i+gap-1,i+2*gap-1);

        if(i+gap-1<length-1){
            merge(array,i,i+gap-1,length-1);
        }

    }

    public static void mergeSortDown2Up(int[] array){
        if(array==null){
            return;
        }
        for (int n=1;n<array.length;n*=2){
            mergeGroups(array,array.length,n);
        }
    }

    public static void main(String[] args) {
        int i;
        int array[]={1,3,2,5,10,9};
        //自上而下的排序方式
        //mergeSortUp2Down(array,0,array.length-1);
        //自下而上的排序方式
        mergeSortDown2Up(array);
        for(int val:array){
            System.out.println("值："+val);
        }
    }








}
